Major Projects Index

<Side Projects Link>

Design and Build a Compiler

For this project, I built a compiler from scratch in C# for a language of my design.

The language grows and adds features based on what the user is attempting to do, explaining new features as they come in an attempt to teach programming as it is performed.

Architecture

The components of a compiler are laid out in “Modern Compiler Implementation in Java” by Appel, my system uses a modification of this standard architecture, both to support the growing language functionality and to remove functionality that the .NET runtime makes redundant (e.g. the CIL handling functions first class and not requiring you to implement them)

Diagram Description automatically generated

Lexer

My lexer is a simple state machine that is documented in the DFA diagram below, this step simply takes user input and collects characters into more meaningful tokens.

Lexer DFA

Parser

I used recursive descent to implement the parser described in the BNF diagram below, this step takes the tokens from the Lexer and computes a tree to represent their structural meaning.

Parser BNF diagram

Semantic Analysis, Code Generation

For these steps, we can simply recursively traverse the AST, and either check conditions on our children, or define recursive rules that convert Nodes into executable code

Error Testing (Custom testing format)

To test my language, I created a simple custom file format to enumerate test cases and check their outputs, be that Errors or text.

A screenshot of a computer program Description automatically generated

Behaviour Testing

The same format is used here for non-error testing

A screenshot of a computer program Description automatically generated

Build a high-level language/shell from an assembly language

Given the following assembly instructions, make a simple OS with shell and a high-level language:

(i and * are to indicate optional immediate/indirect addressing respectively, commands work with direct addressing by default)

lda(i/*): Load value in accumulator

sta(*): Store accumulator in memory

add(i): Add to acc

sub(i): Sub from acc

mul(i): Multiply with and store in acc

and(i): bitwise And with acc

or(i): bitwise Or

xor(i): bitwise Xor

not: bitwise Not

rshift(i): right shift acc by value

lshift(i): left shift acc by value

jmp(i): jump execution to address

jz(i): jump if previous calculation resulted in 0

jnz(i): jump if non-zero

jn(i): jump if negative

stop: End execution

Assume Lazy Terminal Interface:

printa: print acc as signed int (Optional but good for debug, Implement in hardware with BCD to so many digits)

printachar: print acc as character

getchar: get single character from keyboard

Macros

I began by implementing a macro system that would allow me to write assembly code in a way that more closely resembles C-Style programming (in practise to build this computer “from scratch” you would need to expand these macros on paper by hand)

A screenshot of a computer Description automatically generated

A black background with white text Description automatically generated

A screenshot of a computer Description automatically generated

When this project is completely finished this process will be well documented in code to attempt to make reading the source as obstacle free as possible.

Forth Kernel

I decided to build a forth as the next level of abstraction for this machine due to its relatively simple implementation and excellent meta-programming abilities, as well as its REPL environment which makes the language double as a SHELL due to low level access, the snapshots above are taken from a file containing assembly with macros that implements a basic forth kernel, heavily guided by the excellent jonesforth.

The resulting kernel is a very barebones forth, but because forth is forth, we can extend it, within forth!!!

Extended Forth

We begin by defining soft built-in types for our system e.g.

A screenshot of a computer Description automatically generated

We then create a section in memory to act as a separate local variable stack

A screenshot of a computer Description automatically generated

And can now define a syntax for functions

A screenshot of a computer Description automatically generated

We then define structs

A screenshot of a computer program Description automatically generated

Which is simply a syntax that generates many functions via meta-programming to handle areas of data as a “firstStructType”

These structs also contain an initial element that indicates their type, giving us dynamic typing!!

A screenshot of a computer Description automatically generated

A screenshot of a computer Description automatically generated

We can make pseudo-OOP types using structures and functions/methods that are intended to act upon those structs

Showcasing this in action:

Next up will be dynamic memory and eventually implementing an actual parser to enforce Syntax (to catch human error), Come back later to see more.

Interpret machine code/assembly using logic gates

How do we get from nothing to programming? if you’ve looked at the previous section you’ve seen how I have personally started from assembly/machine code, but how do you even get that running? How do you program with no programming language?

Well, it turns out, there is a “programming language” that can be implemented quite simply with electrical circuits… Logic Gates!!!

My first attempt at simulating this process happened many years ago

A picture containing diagram, sketch, plan, technical drawing Description automatically generated

I tried with a drag and drop simulator, it got unruly.

More recently I have reattempted using Verilog, a language that can be used as a markup for systems of Logic Gates

DFlipFlop

Register

For simplicity, the initial design of this system will use an 8-bit word length, so we will simply connect 8 of these DFlipFlops to make 1 register

RAM

To implement ram, we can think of an address in binary e.g. 011001 as a list of switches

To build the RAM recursively, we start with a single register

A black rectangle with a white background Description automatically generated

And then we take 2 of those, and use the lowest bit to decide which to go to (if its 0 go left, if 1 go right)

A black and white rectangles Description automatically generated

Now we can take 2 of those, and use the next lowest bit to choose between those

A black line drawing of a four square frame Description automatically generated with medium confidence

We now have 4 registers indexed by a 2-bit address

If we repeat this recursive process we can end up with a RAM with 2^n number of registers/addresses

A computer screen shot of text Description automatically generated

A screen shot of a computer Description automatically generated

Logic

Addition

We now have memory and registers to operate on, but how do we define the actual logic to do operations? Well one example I will give here is the adder, we can use logic gates to define a circuit that takes 2 binary registers and calculates their sum into another register, you can look up many explanations for this online but here I will show you my Verilog implementation

A screenshot of a computer program Description automatically generated

A screenshot of a computer Description automatically generated

Subtraction

Believe it or not, subtraction is just addition in a computer as we can only store numbers of a certain size

Other operations

These all work in similar ways, there is a logic gate “program” that can perform these operations, in fact logic gates can write any program that a normal programming language could produce, they are “Turing Complete”

Clock

The clock matters for determining change in state, calculations always update based on the current state, therefore to allow sequential execution we must

These 2 rules allow exactly 1 step to run each clock pulse based on control signals we set (steps can include processes that can run in parallel), this allows us to sequentially execute microcode (operations that build up a single instruction)

Sequential Execution

If we have a register that stores our current address to execute (called the Program Counter or PC), then the current code to execute is RAM[PC], but this is just a number, how does the computer know what it needs to do?

Well we simply use combinatorial logic, or to explain more simply, we don’t need to think of the current state as context, but simply as an input to a stateless function, if this was the case then we could implement the functionality as an operation, the same as addition or multiplication. if we want a certain number in memory to mean that our acc should be set equal to acc + bregister, then we could consider a function that takes the computers current state, and returns the state of the computer afterwards f(state, PC) -> newState. We know that any operation/function can be implemented with Logic Gates, and therefore, we can implement this function, Let’s say that RAM[PC] = 65, we just need to ensure that f(state,65) returns the correct output state for every input state and we have our function. In short, we can implement Sequential execution as a function from state to state that is triggered every clock pulse.

Hack Pwnie Island to play flappy bird

This was a team project that I completed for my university course for which we received the highest marks in the University.

A white paper with black text Description automatically generated

For this project we created several hacks using DLL Injection

A screenshot of a computer program Description automatically generated

However our primary hack turned this:

A screenshot of a video game Description automatically generated

Into this:

I operated as Joint Team Leader on this project, and I believe that the culture of our team, focussing on cultivating a fun experience controlled by easily understandable protocol, as well as providing technical help from our different areas of expertise and motivating the fair sharing of ideas, was the primary reason for us reaching the best mark overall.

Side Projects

Clock

Website

Group Project Admin Bot

Mapping In Space with Markiplier

Cheat Engine Scripting

Thousands of others…